package com.shuyun.xxx.guava.algorithm;

import java.util.Arrays;

/**
 * Created by goodb on 2017/5/6.
 */
public class Sort {

    public static final int LEN = 15;

    private static final int[] ARR = new int[LEN];

    public static void exchange(int[] arr, int a, int b){
        arr[a] = arr[a] ^ arr[b];
        arr[b] = arr[a] ^ arr[b];
        arr[a] = arr[a] ^ arr[b];
    }

    public static void main(String[] args){
        int[] arr = generateArray();
        System.out.println(Arrays.toString(arr));
//        bubbleSort(arr);
//        quickSort(arr, 0, arr.length - 1);
//        selectSort(arr);
//        insertSort(arr);
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }


    public static void bubbleSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            for(int j = 0; j < arr.length - 1; j++){
                if(arr[j] > arr[j + 1]){
                    exchange(arr, j, j + 1);
                }
            }
        }
    }

    public static void quickSort(int[] arr, int left, int right){
        int base = arr[left];
        int l = left;
        int r = right;
        boolean go = true;
        do{
            if(go){
                if(base > arr[r]){
                    exchange(arr, l, r);
                    go = !go;
                    continue;
                }else{
                    r--;
                }
            }else if(base < arr[l]){
                exchange(arr, l, r);
                go = !go;
                continue;
            }else{
                l++;
            }
        }while(l < r);
        if(r - left > 1){
            quickSort(arr, left, r - 1);
        }
        if(right - l > 1){
            quickSort(arr, l + 1, right);
        }

    }

    public static void selectSort(int[] arr){
        int index;
        for(int i = 0; i < arr.length - 1; i++){
            index = i;
            for(int j = i + 1; j < arr.length; j++){
                if(arr[j] < arr[index]){
                    index = j;
                }
            }
            if(index != i){
                exchange(arr, index, i);
            }
        }
    }

    public static void insertSort(int[] arr){
        int temp, j;
        for(int i = 1; i < arr.length; i++){
            temp = arr[i];
            j = i - 1;
            while(j >= 0 && arr[j] > temp){
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
        }
    }

    public static void shellSort(int[] arr){
        int temp, j;
        for(int i = arr.length/2; i > 0; i /= 2){
            for(int r = i; r < arr.length; r++){
                temp = arr[r];
                j = r - i;
                while(j >= 0 && arr[j] > temp){
                    arr[j + i] = arr[j];
                    j -= i;
                }
                arr[j + i] = temp;
            }
        }
    }

    public static int[] generateArray(){
        for(int i = 0; i < LEN; i++){
            ARR[i] = (int) (Math.random()*(100));
        }
        return ARR;
    }
}
